package NO6_Tree;

/**
 * 2025-09-15
 * 力扣 - 98. 验证二叉搜索树
 * <p>
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * 有效 二叉搜索树定义如下：
 * 节点的左子树只包含 严格小于 当前节点的数。
 * 节点的右子树只包含 严格大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 */
public class IsValidBST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        TreeNode.printTree(root);
        System.out.println(isValidBST(root));
    }

    public static boolean isValidBST(TreeNode root) {
        return inorderTraversal(root, new Integer[1]);
    }

    // 中序遍历
    private static boolean inorderTraversal(TreeNode node, Integer[] prev) {
        if (node == null) {
            return true;
        }

        if (!inorderTraversal(node.left, prev)) {
            return false;
        }

        if (prev[0] != null && node.val <= prev[0]) {
            return false;
        }
        prev[0] = node.val;

        return inorderTraversal(node.right, prev);
    }
}
